package codeRandomThoughts.Test37解数独;

public class Solution2 {

    public void solveSudoku(char[][] board) {
        backtracking(board);
    }

    public boolean backtracking(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') continue;
                //尝试填入数字 这里用字符更方便点
                for (char num = '1'; num <= '9'; num++) {
                    if (isValid(i, j, num, board)) {
                        board[i][j] = num;
                        if (backtracking(board)) {
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    private boolean isValid(int row, int col, char num, char[][] board) {
        //需要遵循3个规则
        //1.在每一行只能出现一次
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) return false;
        }

        //2.在每一列只能出现一次
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) return false;
        }

        //3.在每个九宫格只能出现一次
        int startRow = (row) / 3 * 3;
        int startCol = (col) / 3 * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num) return false;
            }
        }
        return true;
    }
}
